import collections


class Solution(object):
    def networkBecomesIdle(self, edges, patience):
        n = len(patience)
        dist = [-1] * n
        dist[0] = 0
        d = collections.defaultdict(set)
        for u, v in edges:
            d[u].add(v)
            d[v].add(u)
        now = {0}
        q = 0
        while now:
            q += 1
            next_set = set()
            for u in now:
                for v in d[u]:
                    if dist[v] == -1:
                        next_set.add(v)
                        dist[v] = q
            now = next_set
        min_time = 0
        for i in range(1, n):
            transfer_time = 2 * dist[i]
            wait_time = ((transfer_time - 1) // patience[i]) * patience[i]
            min_time = max(min_time, transfer_time + wait_time)
        return min_time + 1


data = Solution()
edges = [[0, 1], [1, 2]]
patience = [0, 2, 1]
print(data.networkBecomesIdle(edges, patience))
